package com.ronz.search;

/**
 * @Description 二分查找算法
 * @Author Ronz
 * @Date 2021/1/13 18:41
 * @Version 1.0
 */
public class No2_BinarySearch {


    public static void main(String[] args) {
        int[] arr = {2,5,8,9,11,45,67,88,188};
        int index = binarySearch(arr, 0, arr.length - 1, 11);

        System.out.println(index);
    }

    /**
     * 二分查找算法
     * @param arr   从此数组中查找目标元素
     * @param left  查找范围左边界
     * @param right 查找范围右边界
     * @param finalValue    目标元素
     * @return int  目标元素在数组的索引
     */
    public static int binarySearch(int[] arr, int left, int right, int finalValue){
        if (left <= right){      // 只有 left <= right 时，才继续查找
            int mid = (left + right) / 2;   // 中间元素
            if (finalValue == arr[mid]){    // 如果相等，说明找到了
                return mid;
            }else if(finalValue > arr[mid]){    // 如果大于中间元素，则向左递归
                return binarySearch(arr, mid+1, right, finalValue);
            }else if(finalValue < arr[mid]){    // 如果小于中间元素，则向右递归
                return binarySearch(arr, left, mid-1, finalValue);
            }
        }
        return -1;  // 如果遍历完还没找到，就返回 -1
    }

}
